package combination;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program: javase
 * @description: 子集2,含有重复元素：先排序，通过传不同起始的下标，达到不往前面访问
 * @author: luolidong
 * @create: 2021-06-20 11:56
 * @version: 1.0
 */
public class SubSets2 {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> list=new ArrayList<>();
        if(nums.length==0) return list;
        Arrays.sort(nums);
        dfs(list, new ArrayList<>(), 0, nums);
        return list;

    }
    private void dfs(List<List<Integer>> list,List<Integer> clist,int begin,int[] nums){
        if(clist.size()>nums.length) return;
        list.add(new ArrayList<>(clist));
        for (int i = begin; i <nums.length ; i++) {
//            [] [1] [1, 2] [1, 2, 2] [1, 2] [2] [2, 2] [2]
//            这样会把[2,2]过滤掉
//            if(i+1<nums.length&&nums[i]==nums[i+1]) continue;
//            要判断当
            if(i>begin&&nums[i]==nums[i-1]) continue;
            clist.add(nums[i]);
            dfs(list, clist, i+1, nums);
            clist.remove(clist.size()-1);
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> subsets = new SubSets2().subsets(new int[]{1, 2, 2});
        for(List<Integer> s:subsets){
            System.out.print(s+" ");
        }
    }
}
